package com.suanfa.dp;

public class MinSteps {

    public static void main(String[] args) {
        //int[][] arr = {{1, 3 ,5 ,9},{8 ,1 ,3, 4},{5 ,0 ,6, 1},{8, 8, 4, 0}};

int[][]arr
     = {{3, 3, 1, 6, 7, 6, 0, 7, 8, 0},
        {5, 0, 5, 0, 5, 3, 9, 8, 0, 4},
        {2, 8, 8, 9, 0, 6, 8, 7, 6, 7},
        {6, 1, 0, 9, 0, 9, 6, 0, 6, 6},
        {2, 3, 6, 9, 5, 3, 2, 4, 3, 4},
        {1, 5, 2, 1, 4, 5, 8, 4, 2, 6},
        {3, 0, 0, 5, 0, 0, 4, 6, 2, 2},
        {4, 6, 6, 2, 5, 1, 7, 9, 8, 0},
        {3, 1, 7, 7, 2, 4, 2, 0, 8, 6},
        {9, 4, 7, 9, 9, 7, 1, 4, 5, 5}};
        System.out.println(minSteps(arr));
    }


    public static int minSteps(int[][] arr){
        int n = arr.length;//行
        int m = arr[0].length;//列

        int[][]dp = new int[n][m];

        dp[0][0] = arr[0][0];

        for(int i = 1; i < m; i++){
            dp[0][i] = dp[0][i-1] + arr[0][i];
        }
        for(int i = 1; i < n; i++){
            dp[i][0] = dp[i-1][0] + arr[i][0];
        }

        for(int i = 1; i< n; i++){
            for(int j = 1; j<m; j++){
                //左边到达
                int left = dp[i][j-1] + arr[i][j];
                //上方到达
                int top = dp[i-1][j] + arr[i][j];
                dp[i][j] = Math.min(left, top);
            }
        }

        for(int i = 0; i< n; i++){
            for(int j = 0; j<m; j++){
                System.out.print(dp[i][j] + ",");
            }
            System.out.println();
        }


        return dp[n-1][m-1];
    }
}
